package leetcode.bfs;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
 *
 * 如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：
 * grid =
 * [[0,0,0],
 *  [1,1,0],
 *  [0,0,0],
 *  [0,1,1],
 *  [0,0,0]],
 * k = 1
 * 输出：6
 * 解释：
 * 不消除任何障碍的最短路径是 10。
 * 消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
 *  
 *
 * 示例 2：
 *
 * 输入：
 * grid =
 * [[0,1,1],
 *  [1,1,1],
 *  [1,0,0]],
 * k = 1
 * 输出：-1
 * 解释：
 * 我们至少需要消除两个障碍才能找到这样的路径。
 *  
 *
 * 提示：
 *
 * grid.length == m
 * grid[0].length == n
 * 1 <= m, n <= 40
 * 1 <= k <= m*n
 * grid[i][j] == 0 or 1
 * grid[0][0] == grid[m-1][n-1] == 0
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class diffiuclt_网格中的最短路径 {

    static class Solution {
        public int shortestPath(int[][] grid, int k) {
            int m = grid.length;
            int n = grid[0].length;
            Queue<int[]> q = new LinkedList<>();
            int[][][] visited = new int[m][n][k+1];
            for (int i = 0; i < m; i++){
                for (int j = 0; j < n; j++){
                    Arrays.fill(visited[i][j], -1);
                }
            }
            q.offer(new int[]{0, 0, 0});
            visited[0][0][0] = 0;
            int[] directions = new int[]{-1, 0, 1, 0, -1};
            while (!q.isEmpty()){
                int[] curr = q.poll();
                if (curr[0] == m-1 && curr[1] == n-1) return visited[curr[0]][curr[1]][curr[2]];
                for (int i = 0; i < 4; i++){
                    int x = curr[0]+directions[i];
                    int y = curr[1]+directions[i+1];
                    if (x < 0 || x >= m || y < 0 || y >= n) continue;
                    if (grid[x][y] == 1){
                        if (curr[2]+1 > k) continue;
                        if (visited[x][y][curr[2]+1] < 0){
                            visited[x][y][curr[2]+1] = visited[curr[0]][curr[1]][curr[2]] + 1;
                            q.offer(new int[]{x, y, curr[2]+1});
                        }
                    }else {
                        if (visited[x][y][curr[2]] < 0){
                            visited[x][y][curr[2]] = visited[curr[0]][curr[1]][curr[2]] + 1;
                            q.offer(new int[]{x, y, curr[2]});
                        }
                    }
                }
            }
            return -1;
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.shortestPath(new int[][]{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}, 1));
    }
}
